
def knapsack(W, wt, val,n):
    #创建一个二维数组₂dp，用于存储子问题的解
    dp =[[0 for _ in range(W+1)] for _ in range(n + 1)]
    # 初始化边界条件
    for i in range(n + 1):
        dp[i][0]= 0
    for j in range(W + 1):
        dp[0][j]= 0
    #通过动态规划计算每个子问题的解
    for i in range(1, n + 1):
        for j in range(1, W + 1):
            if wt[i-1]<= j:
                dp[i][j]= max(dp[i-1][j-wt[i-1]]+ val[i-1], dp[i-1][j])
            else:
                dp[i][j]= dp[i-1][j]
    # 返回原问题的解
    return dp[n][W]
# 测试
W=10 #背包的最大容量
wt =[2,3,4,5]#物品的重量
val=[3,4,5,6]#物品的价值
n=len(wt)#物品的数里
print("背包问题的最大价值为:",knapsack(W,wt,val,n))

dp =[[0 for _ in range(5)]for _ in range(5)]
print(dp)